﻿#include "BinaryTree.h"

BinaryTreeNode::BinaryTreeNode(int id, int value)
{
    this->value = value;
    uniqueId = id;
    left = nullptr;
    right = nullptr;
}

BinaryTreeNode::~BinaryTreeNode()
{

}

int BinaryTreeNode::getValue()
{
    return value;
}

int BinaryTreeNode::getId()
{
    return uniqueId;
}

static BinaryTreeNode* reverseRight(BinaryTreeNode* head)
{
    auto cur = head;
    BinaryTreeNode* prev = nullptr;
    BinaryTreeNode* nextRight = nullptr;
    while (cur)
    {
        nextRight = cur->right;
        cur->right = prev;
        prev = cur;
        cur = nextRight;
    }

    return prev;
}

void deleteBinaryTree(BinaryTreeNode* head)
{
    // morris 后续遍历删除各个节点
    auto cur = head;
    BinaryTreeNode* reversedHead = nullptr;
    BinaryTreeNode* tmpNode = nullptr;
    BinaryTreeNode* nextRight = nullptr;
    while (cur)
    {
        if (!cur->left)
        {
            cur = cur->right;
            continue;
        }

        auto mostRight = cur->left;
        while (mostRight->right && mostRight->right != cur)
        {
            mostRight = mostRight->right;
        }

        if (!mostRight->right)
        {
            mostRight->right = cur;
            cur = cur->left;
        }
        else if (mostRight->right == cur)
        {
            mostRight->right = nullptr;

            reversedHead = reverseRight(cur->left);
            tmpNode = reversedHead;
            while (tmpNode)
            {
                nextRight = tmpNode->right;
                delete(tmpNode);
                tmpNode = nextRight;
            }

            cur = cur->right;
        }
    }

    reversedHead = reverseRight(head);
    tmpNode = reversedHead;
    while (tmpNode)
    {
        nextRight = tmpNode->right;
        delete(tmpNode);
        tmpNode = nextRight;
    }
}

#define MAX(a, b) (a > b ? a : b)

int calcBinaryTreeNodeMaxDepth(BinaryTreeNode* head)
{
    if (!head) return 0;

    int left = calcBinaryTreeNodeMaxDepth(head->left);
    int right = calcBinaryTreeNodeMaxDepth(head->right);
    return 1 + MAX(left, right);
}
